package chixing.day15.homework.work5;

import java.util.HashMap;
import java.util.Map;

/**
 * 设计一个数据结构，实现LRU Cache的功能(Least Recently Used – 最近最少使用缓存)。
 *  删除最近最少被使用的
 */
public class LRUCache {
    private HashMap<Integer, Integer> map;//存放键和value

    static HashMap<Integer, Integer> contMap = new HashMap<>();//存放键和该键的使用次数
    static int k = 0;//存放使用次数最少的键

    public LRUCache() {
        map = new HashMap<>(2);
    }

    /**
     * 传入key 获取value
     *
     * @return 如果key已存在，则返回key对应的值value（始终大于0）
     * 如果key不存在，则返回-1
     * get一次该键的使用次数要 +1
     * <p>
     * 可以先判断contMap中是否为空，如果为空那肯定是第一个，就直接加进去，然后把该元素的key给变量k【假设为使用次数最少的key】
     * 如果不为空，先把该元素添加到contMap 然后去和k的使用次数进行比较若小于key的使用次数 就用当前元素把变量k替换，
     */

    public int get(int key) {//
        //判断输入的key在这个map中 是否存在
        if (map.containsKey(key)) {//如果存在 输出value
            contMap.put(key, contMap.get(key)+1);//使用了一次该键，使用次数要+1
            //然后去和k的使用次数进行比较若小于key的使用次数 就用当前元素把变量k替换
//            System.out.println(k+"-k使用次数："+contMap.get(k)+","+key+"-key使用次数："+contMap.get(key));
            if (contMap.get(k) > contMap.get(key))
                k = key;//该key使用次数最少
//            System.out.println("此时的k是"+ k);
            return map.get(key);
        }
        //不存在返回-1
        return -1;
    }

    /**
     * 如果key不存在，将value插入；如果key已存在，则使用value替换原先已经存在的值。
     * 如果容量达到了限制，LRU Cache需要在插入新元素之前，将最近最少使用的元素删除。
     * 请特别注意“使用”的定义：新插入或获取key视为被使用一次；而将已经存在的值替换更新，不算被使用。
     * ：请在O(1)的时间复杂度内完成上述2个操作。
     *
     * @param key   要插入的key值
     * @param value 要插入的value值
     */
    public void put(int key, int value) {
        //如果容量达到了限制，LRU Cache需要在插入新元素之前，将最近最少使用的元素删除。
        if (map.size() >= 2 && !map.containsKey(key)) {
            map.remove(k);
        }
        //在contMap添加第一个元素的时候给k赋值
        if (contMap.isEmpty()){
            map.put(key, value);
            contMap.put(key, 1);
            k=key;
        }else if (!contMap.containsKey(key)){
            // 如果key不存在，将value插入【增加使用次数】
            map.put(key, value);
            contMap.put(key, 1);
            if (contMap.get(k) >= contMap.get(key))
                k = key;//该key使用次数最少
        }else {
            //如果key已存在，则使用value替换原先已经存在的值【不增加使用次数】。
            map.put(key, value);
        }


    }

    public void displayMap() {
        for (Map.Entry<Integer, Integer> e : map.entrySet()) {
            System.out.println(e);
        }
    }
    public void displayContMap() {
        for (Map.Entry<Integer, Integer> e : contMap.entrySet()) {
            System.out.println(e);
        }
    }
}
